白话一致性协议 - Paxos、Raft和PacificA[2]

PacificA是一个框架

虽然在题目中我们把Paxos、Raft和PacificA并列，但是Paxos和Raft在论文中称自己为一种“算法”（algorithm）；而PacificA对自己的定位是一种通用的，强一致的数据同步框架。

在论文中，作者提到现有的可证明的数据同步协议往往过分简化了性能问题，导致看起来很美的理论设计无法转变有实际的系统（注：本篇论文应该早于Raft的论文）。所以作者的目标是将算法理论与实际相结合，进行相应的系统设计。

PacificA的实现

与Paxos和Raft不同的是，PacificA采用的算法非常简单。所以在这里我不进行太多铺垫，直接进入正题。

主从同步

PacificA使用了主从同步模型，用户的读写请求都会发往主节点，以保证强一致性。

主节点会对发来的写请求进行编号，使得所有写请求编号唯一且单调递增。这个编号也会同步到从节点。

无论是主节点还是从节点，所有的写请求都写入一个只追加的日志。主从节点都需要维护committed指针，代表在这个指针之前的数据都已经被所有节点所认可，处理“已确认”状态。从节点需要额外维护一个prepared指针，代表在这个指针之前所有的数据都处于“待确认”状态，而在prepared指针之后的数据，都是“待同步”状态。

主从之间的数据同步使用两步提交模型（2-PC）：

主节点首先把写请求写入日志
主节点发送prepare请求到从节点，这个请求中包含写入的数据
从节点收到prepare请求后，将数据加入日志，并移动prepared指针，将其标记为“待确认”
当所有从节点返回ACK后，主节点移动committed指针，表明这个数据处于“待确认”状态
主节点向所有从节点发送ACK消息，确认这条请求已经被最终确认
从节点收到ACK消息后，移动committed指针，确认请求

所以对于一个节点，总会有:

全局配置管理器

PacificA使用了一个“中心化的”全局配置管理器。这个管理器用于探测系统内的失效节点，管理、更新节点的配置。而Raft是“去中心化的”，通过节点之间的选举通信来管理配置。

PacificA的全局配置管理器保证在任何情况下，当且仅当全局配置管理器认可节点s为主节点时，节点s才会认为自己是主节点。

全局配置管理器在“钦点”了主节点后，主节点会与从节点发送心跳包（beacons），维护一个租期（lease）。在租期内，主节点和从节点都会互相承认相互之间的主从关系。当租期失效时，主节点会向全局配置管理器报告从节点失效。当从节点收不到心跳包时，从节点会报告主节点失效。

一个中心化的配置管理器会让整个系统的维护变的非常简单，但是也会带来单点失效的隐患。这里，全局配置管理器使用了Paxos算法来保证管理器节点之间的一致性，可以容忍少于半数节点的失效。

配置变化与灾难恢复

由于我们使用的全局的配置管理器，所以添加删除从节点会是非常简单的事情。这里我们主要讨论主节点的失效与灾难恢复。

当主节点失效之后，从节点会揭竿而起，向配置管理器申请成为主节点。这里要注意，根据上面的讨论，从节点中的committed指针有可能会落后于主节点，以及不同从节点中的committed指针可能会不一致。但是被主节点ACK的数据，一定位于从节点的日志中，并处于“待确认”状态。

所以在新的主节点被指派之后，会重新的向其它的从节点发出prepare指令，要求确认其日志中待确认的数据。从而保持数据的一致性

PacificA的正确性的简单讨论

一个强一致性的系统一定会包含以下三种特性：

线性一致性（Linearizability）
由于我们的写请求位于一个只可追加写的日志当中，并且不同的副本的日志保持强一致。所以不同的副本的状态也应该是一致的。
可持久性（Durability）
如果用户收到了ACK，那么这个请求一定已经持久化到所有的副本之上了。即使发生了主节点失效，新的主节点仍会维持已ACK的数据。
前进性（Progress，不知道怎么翻译）
全局配置管理器在处理完配置更新请求后，一定可以剔除失效的节点。使得整个系统可以处理用户的读写请求。

一些其它的讨论

全局配置管理器的可用性和性能

由于全局配置管理器在逻辑上是整个系统的单点，所以其可用性和性能是非常值得关注的。

全局配置管理器了Paxos算法，所以在少于一半的节点失效时，它仍能对外提供服务。

同时，全局配置管理器的处理不在整个系统的关键路径上，所以在一般情况下不会影响系统的整体性能。同时，在系统不正常运行的情况下，即使配置管理器暂时失效，也不会影响系统的运行。

可持久性

PacificA的日志同步采用了两步提交，所以用户收到ACK时，说明用户的写请求已经被持久化在所有的节点之上了。

这意味着，在一个有n台机器的集群里，即使有n - 1台节点失效，我们仍能提供可用的服务。（但是一般只提供只读服务）

主从复制 vs. Paxos

在Paxos范式的实现中，如果一个请求被多数节点认可，我们就可以向用户端返回ACK，声明这个请求已经被整个系统所认可。但是在主从复制的范式下，必须要所有的节点都认可这个请求，我们才可以说这个请求被整个系统所认可。

因为这两种范式之间的不同策略导致了微妙的差别。

我们很容易看出，Paxos范式中对于单个节点的性能波动并不敏感，但是主从复制的一个慢节点可能会拖慢整个系统。但是，如果系统中多数节点全部失效，那么Paxos范式就无法提供服务了（读/写都不可以的）；对于主从复制范式，只要有一个节点是存活的状态，我们就可以对外提供服务，并且保持强一致性。

更重要的是，使用单点来管理整个系统的配置，并让开发与运维的成本降低。换做Paxos范式，一个节点若要成为主节点，则需要同多数节点进行协商。

这两种范式的选择是非常有争议的，PecificA选择主从复制的主要原因就是因为它简单。（太实在了）

在强一致性上的妥协

如果需要放松对强一致性的要求，我们可以让从节点支持读请求。这样带来的问题是我们有可能读到陈旧的数据，由强一致性退化到最终一致性。

最终一致性从本质上说需要满足以下两个要求：

所有的节点需要以同样的顺序执行同样的状态更新操作
在处理请求时，必须返回最新的状态

如果放松第一个要求，就会面临“状态分叉”的问题（像git branch一样），所以我们需要处理这种不一致的问题（像git rebase一样）。这就会带来额外的复杂性和不确定性。

放松第二个要求是更加理性的，因为在PecificA中，所有的状态变化全都被写入一个“只可追加写”的日志中。并且当前的状态变化通过日志指针的移动来表示。又因为从节点的日志一定是主节点的前辍，并且日志指针稍微落后与主节点。所以如果我们可以放松强一致性的要求，就可以让从节点来处理读请求。

写在后面

还有好多东西没读透呢。要不再饶一篇？